package com.study.algorithm.binarytree;

/**
 * 108. 将有序数组转换为二叉搜索树
 */
public class SortedArrayToBST {
    public TreeNode sortedArrayToBST(int[] nums) {
        // 调用递归函数，处理整个数组
        return buildBST(nums, 0, nums.length - 1);
    }

    /**
     * 递归构建平衡BST
     * @param nums 有序数组
     * @param left 当前子数组的左边界
     * @param right 当前子数组的右边界
     * @return 构建好的子树根节点
     */
    private TreeNode buildBST(int[] nums, int left, int right) {
        // 基准情况：左边界超过右边界，说明没有元素了
        if (left > right) {
            return null;
        }

        // 选择中间位置的元素作为根节点
        // 这样能保证左右子树节点数尽可能相等，从而实现平衡
        int mid = left + (right - left) / 2;

        // 创建根节点
        TreeNode root = new TreeNode(nums[mid]);

        // 递归构建左子树：使用左半部分数组
        root.left = buildBST(nums, left, mid - 1);

        // 递归构建右子树：使用右半部分数组
        root.right = buildBST(nums, mid + 1, right);

        return root;
    }
}
